\input{euler.tex}

\begin{document}

\problem[271]{Modular Cubes, Part I}

For a positive number $n$, define $S(n)$ as the sum of the integers $x$, for which $1 < x < n$ and
$x^3 \equiv 1 (\text{mod } n)$. 

When $n=91$, there are 8 possible values for $x$, namely: 9, 16, 22, 29, 53, 74, 79, 81.
Thus, $S(91)=9+16+22+29+53+74+79+81=363$.

Find $S(13082761331670030)$.

\solution

The requested number, 13082761331670030, is a product of the first 14 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43. To solve $x^3 \equiv 1 \mod n$, we can equivalently solve a system of equations $x^3 \equiv 1 \mod p$ for each of $n$'s prime factors, $p$.

For a given prime number $p$, rewrite $x^3 \equiv 1 \mod{p}$ as
\begin{equation}
(x-1)(x^2+x+1) \equiv 0 \mod{p} \label{eq:2}
\end{equation}
It follows that $x \equiv 1$ or $x^2+x+1 \equiv 0$. Note that both equations can hold only when $p=3$.

To solve the second quadratic congruence equation, suppose $x$, $a$ are two of its roots, then 
\[
x^2+x+1 \equiv a^2+a+1 \mod p ,
\] 
which yields
\[
(x-a)(x+a+1) \equiv 0 \mod p .
\]
It follows that either $x \equiv a$ or $x \equiv p-1-a$. Therefore, once we find the smallest root $0 \le a < p$ (if one exists), the rest solutions are readily available. Since $a$ is supposed to be the smallest root, it follows from the second equation that $a \le \lfloor (p-1)/2 \rfloor$. This implies that there are no solution for $p=2$, only one solution for $p=3$, and either two or no solutions for $p \ge 5$.

Suppose $n$ has $m$ prime factors. For each prime factor $p_i$, $1 \le i \le m$, equation \eqref{eq:2} has at most three roots below $p_i$. For each combination of roots from each factor, $(a_1, \ldots, a_m)$, we obtain a system of linear congruence with $m$ equations:
\begin{equation}
x \equiv a_i \mod p_i \notag .
\end{equation}
Below is a list of the cubic congruence roots of 1 modulo each of the first 14 primes:
\begin{center}
\begin{tabular}{c|l|c|l}
\hline
Modulus & Roots & Modulus & Roots \\
\hline
 2 & 1 &  19 & 1, 7, 11 \\
 3 & 1 & 23 & 1 \\
 5 & 1 & 29 & 1 \\
 7 & 1, 2, 4 & 31 & 1, 5, 25 \\
 11 & 1 & 37 & 1, 10, 26 \\
 13 & 1, 3, 9 & 41 & 1 \\
 17 & 1 & 43 & 1, 6, 36 \\
 \hline
\end{tabular}
\end{center}

We can solve a linear congruence system using the Chinese remainder theorem. For each system, there is exactly one solution below $n$, and the solutions to different systems are different. In particular, $x=1$ is the solution to the system $a_i=1, 1 \le i \le m$. The total number of solutions is below $3^m$. We can find them one by one and add them up to get the answer to the problem.

\answer

4617456485273129588

\complexity

Time complexity: $\BigO(m \cdot 3^m)$

Space complexity: $\BigO(m)$

\reference

http://en.wikipedia.org/wiki/Quadratic\_residue

http://en.wikipedia.org/wiki/Chinese\_remainder\_theorem

http://en.wikipedia.org/wiki/Extended\_Euclidean\_algorithm

\end{document} 